package a11_单调栈;

import java.util.Stack;

/**
 * <p>
 * a04_接雨水
 * </p>
 *
 * @author flyduck
 * @since 2025/3/7
 */
public class a04_接雨水 {

    public static void main(String[] args) {
        a04_接雨水 test = new a04_接雨水();
        System.out.println(test.trap(new int[]{4, 2, 0, 3, 2, 5}));
    }

    //为啥左边大的取相等也可以，如果不取相等的，那么这两个元素会重复计算两次
    public int trap(int[] nums) {
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]){
                Integer pop = stack.pop();
                if(!stack.isEmpty()){
                    int height = Math.min(nums[stack.peek()], nums[i]) - nums[pop];
                    int weight = i - stack.peek() - 1;
                    result += height * weight;
                }
            }
            stack.push(i);
        }

        return result;
    }
}
